package main

import (
	"fmt"
	"math/rand"
	"oslab/model"
	"time"
)

var (
	size           = 0
	missingPageNum = 0
	mmap           map[int]int
)

// bestPermutationAlgorithm 最佳置换算法，选择的被淘汰的页面将是以后永久不使用的，或者是最长时间不再被访问的页面
func bestPermutationAlgorithm(siz int) {
	size = siz
	mmap = make(map[int]int, 0)

	order := random()
	order2 := make([]int, len(order))
	copy(order2, order)
	j := 0
	for i := 0; i < len(order); i++ {
		key := order[i] / 10
		address := key*1000 + order[i]%10*100
		// 对应页面不在内存中，产生缺页异常
		fmt.Println("获取指令序列", key)
		if _, ok := mmap[key]; !ok {
			fmt.Println("发生缺页，进行页面置换")
			missingPageNum++
			if len(mmap) < size {
				mmap[key] = address
			} else {
				// 淘汰, 最远距离
				oindex, max := 0, 0
				for k, _ := range mmap {
					// search which will be eliminated
					for j = i + 1; j < len(order); j++ {
						if order[j]/10 == k {
							if j-i > max {
								oindex = k
								max = j - i
							}
							break
						}
					}
					if j == len(order) {
						oindex = k
						max = j - i
					}
				}
				// 淘汰页面
				fmt.Println("淘汰页面", oindex)
				delete(mmap, oindex)
				mmap[key] = address
			}
			printMK()
			fmt.Println("当前指令序列", order[i], ",地址为", mmap[key], ",所在页", key)
		} else {
			fmt.Println("指令在内存中")
			fmt.Println("当前指令序列", order[i], ",地址为", mmap[key], ",所在页", key)
		}
	}
	fmt.Println("OPT页面引用串为", order2)
	fmt.Println("OPT缺页次数为", missingPageNum, ", 缺页率为", float32(missingPageNum)/float32(len(order)))

}

func printMK() {
	kset := make([]int, 0, len(mmap))
	for k, _ := range mmap {
		kset = append(kset, k)
	}
	fmt.Println("当前内存中的页面:'", kset, "'")
}

/*
	通过随机数产生一个指令序列，共320条指令。
		1）指令的地址按下述原则生成：
			① 50%的指令是顺序执行的；
			② 25%的指令是均匀分布在前地址部分；
			③ 25%的指令是均匀分布在后地址部分；
		具体的实施方法是：
			① 在[0，319]的指令地址之间随机选取一起点m；
			② 顺序执行一条指令，即执行序号为m+1的指令；
			③ 在前地址[0，m-1]中随机选取一条指令并执行，该指令的序号为m1；
			④ 顺序执行一条指令，其序号为m1+1的指令；
			⑤ 在后地址[m1+2，319]中随机选取一条指令并执行,该指令的序号为m2；
			⑥ 顺序执行一条指令，其序号为m2+1的指令；
				   重复上述步骤①～⑥，直到执行320次指令。
		2）将指令序列变换为页地址流
			设页面大小为1K， 用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
			第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
			第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
			……
			……
			第310条～第319条指令为第31页（对应虚存地址为[310，319]）。
			按以上方式，用户指令可组成32页。
*/
func random() []int {
	i, m := 0, 0
	orderNum := make([]int, 320)
	rand.Seed(time.Now().UnixNano())
	for i < 320 {
		orderNum[i] = rand.Intn(320) + 1
		// 随机选取的起点
		m = orderNum[i]
		// 计数
		i++
		// 前地址区
		if i >= 320 {
			break
		}
		orderNum[i] = rand.Intn(m)
		m = orderNum[i]
		i++
		if i >= 320 {
			break
		}

		orderNum[i] = m + 1
		i++
		if i >= 320 {
			break
		}

		orderNum[i] = rand.Intn(320-m-2) + m + 2
		m = orderNum[i]
		i++
		if i >= 320 {
			break
		}
		orderNum[i] = m + 1
		i++
	}
	return orderNum
}

// LRU 最近最少使用
func LRU(siz int) {
	size = siz
	order := random()
	order2 := make([]int, len(order))
	copy(order2, order)
	lru := model.Constructor(size)

	for i := 0; i < len(order); i++ {
		key := order[i] / 10
		fmt.Println("获取指令", order[i])
		if address := lru.Get(key); address == -1 {
			fmt.Println("发生缺页，进行页面置换")
			// search which will be eliminated
			missingPageNum++
			address = key*1000 + order[i]%10*100
			lru.Put(key, address)
			// print
			kset := make([]int, 0, len(lru.Keys))
			for k := range lru.Keys {
				kset = append(kset, k)
			}
			fmt.Println("当前内存中的页面:'", kset, "'")
			fmt.Println("当前指令序列", order[i], ",地址为", address, ",所在页", key)
		} else {
			fmt.Println("指令在内存中")
			fmt.Println("当前指令序列", order[i], ",地址为", address, ",所在页", key)
		}
	}
	fmt.Println("OPT页面引用串为", order2)
	fmt.Println("OPT缺页次数为", missingPageNum, ", 缺页率为", float32(missingPageNum)/float32(len(order)))
}
